package lc;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Q503 {

    public static void main(String[] args) {
        Q503 q503 = new Q503();
        int[] ints = q503.nextGreaterElements(new int[]{1, 2,8, 3, 4, 5,1,4});
        System.out.println(Arrays.toString(ints));
    }

    public int[] nextGreaterElements(int[] nums) {
        // 单调递减栈
        Deque<Integer> deque = new LinkedList<>();
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        for (int i = 0; i < 2; i++) {
            // 循环两轮就行
            for (int k = 0; k < n; k++) {
                while (!deque.isEmpty() && nums[k] > nums[deque.peekLast()]) {
                    Integer last = deque.pollLast();
                    result[last] = nums[k];
                }
                deque.addLast(k);
            }
        }
        return result;
    }

}
